1. Field of the Invention
The present invention relates to a fuzzy method and device for the recognition of geometric shapes in images. The fields of application of this method and of this device range from automatic guidance and navigation systems to image understanding systems.
2. Discussion of the Related Art
The primary goal of vision systems is to recognize objects in an image. However, before the object can be recognized it is necessary to recognize the characteristic lines that compose it and provide a symbolic representation of the object. One way to achieve these goals is to use the Hough transform, which is capable of performing a mapping from structures of the feature space to structures of an appropriate parameter space.
Straight lines can be considered as an example of this Hough transform also because they are undoubtedly the lines that most frequently occur in the description of the shape of objects. It is thus evident that providing a method capable of identifying and describing these lines, which so often compose an object, is extremely important.
The Hough transform, introduced in 1962, was in fact developed to solve this problem and generalized only at a later time so as to consider other types of parameter lines.
Consider a point that has the coordinates (x.sub.i, y.sub.i) and belongs to a generic straight line defined by the equation y=ax+b. It is evident that an infinite number of lines pass through this point; however, all such straight lines must satisfy the equation y.sub.i =ax+b for different values of a and b.
Therefore, by writing this last equation in the form b=y.sub.i -ax.sub.i and considering the plane ab (parameter plane) it is possible to obtain the equation of a single straight line at a point having preset coordinates.
The same line of reasoning can of course be followed for another point that has the coordinates (x.sub.j, y.sub.j); a new straight line associated with this point will be obtained in the parameter space. The intersection of the two straight lines generated in the parameter plane allows one to obtain the parametric coordinates (a,b) of the straight line that connects the two points of the feature plane. FIGS. 1A and 1B illustrate this graphically.
The parametric equation for straight lines proposed above has some severe drawbacks: even for limited portions of the feature space, the domain of values of both parameters a and b can be the entire set of real numbers (for example, in vertical straight lines a=.infin.).
In order to obviate this drawback, the following representation is usually adopted instead: EQU p=X cos.theta.+sin.theta.
where p is the distance of the straight line from the origin and .theta. is the angle formed by the axis x and by the normal to the straight line, as shown in FIG. 2.
By using this representation, each point of the feature space is matched by a sinusoid in the parameter space. Clearly the parameter space is limited, since p is within the range -R.sqroot.2, R.sqroot.2! for images with a linear dimension R and .theta. can be limited between 0.degree. and 180.degree., since 180.degree. translations in .theta. and an optional reversal of sign in p allow to return to the range 0.degree., 180.degree.!.
Accordingly, if one has a set of n points (X1, X2), . . . ,(Xn,Yn)! that belong to a given straight line in the feature plane and one wishes to determine the parameters that describe this straight line, it is necessary to transform the points (Xi, Yi) into sinusoidal curves in the plane p-.theta., which are described by p=Xi cos.theta.+Yi sin.theta., and to note that these curves all intersect at the parametric values of the straight line being sought, as shown in FIGS. 3A and 3B. In other words, by transforming co-linear pixels in the feature plane one obtains several sinusoids that intersect in a single point that has the coordinates (.theta..sub.0,p.sub.0) and corresponds to the straight line on which said points lie. Accordingly, the problem of finding collinear points in the feature can be converted into the problem of finding concurrent curves.
The computational advantage of the Hough transform arises from dividing the parameter space into cells, that is to say, from introducing an acceptable error in p and .theta. in the quantization of the parameters in a grid. Quantization can be reduced to the region 0.ltoreq..theta..ltoreq..pi. and -R.ltoreq.p.ltoreq.R, where R is the maximum distance that a point of the feature plane can have from the center of the image (in practice, half of a diagonal). The quantized region can thus be reduced to a two-dimensional array of accumulators. For each point (Xi, Yi) in the feature plane, the corresponding curve is mapped onto the array, increasing the accumulator in each cell that lies along the curve. Accordingly, each cell of the parameter space stores the number of curves that have passed through it, minus the noise and the discretization that is carried out.
After transforming all the points of the edge, the problem is to find the local maximums in the array of accumulators. These local maximums must be higher than a certain threshold in order to extract only lines that are long enough, and most of all in order to eliminate noise (false maximums). It is therefore necessary to find a threshold that varies in each situation in the most intelligent possible manner according to the image to be analyzed.
After extracting the local maximums from the array of accumulators it is possible to draw the lines that they have generated. In other words, the inverse transform is applied, reconstructing the corresponding straight line for each maximum point (.theta., p) by using the following equation: ##EQU1## It should be noted that the Hough transform can also be used for other geometric shapes, such as curves, circles, etcetera.
However, the transformation performed with the Hough transform is sensitive to the noise that is present in the image and depends on the performance of the edge detection system that is used. Another problem in the use of the Hough transform is the recovery of points lost due to discretizations and noise.
A problem of vision systems in general is processing speed. Known systems have a very high level of processing complexity and have processing speeds that are not satisfactory for the required applications, (for example, theoretically real-time processing). Another problem of known vision systems is the complexity of the hardware.